package sonSTRING;

import java.util.*;

public class subarraySum {
    /*
    给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。
子数组是数组中元素的连续非空序列。
示例 1：
输入：nums = [1,1,1], k = 2
输出：2
示例 2：
输入：nums = [1,2,3], k = 3
输出：2
     */
    public static int subarraySum(int[] nums, int k) {
        int count = 0;
        Map<Integer,Integer> map =  new HashMap<>();
        int p =0;
        map.put(0,1);
        for(int i = 0;i<nums.length;i++){
            p+=nums[i];
            if(map.containsKey(p-k))
                count+=map.get(p-k);
            map.put(p,map.getOrDefault(p,0)+1);
        }
        return count;
}
    public static int subarraySum1(int[] nums, int k){
        int sum=0;
        int count=0;
        int i=0;
        for(;i<nums.length;i++){
            if(k-nums[i]==0){
                count++;
            }
            for(int j=i+1;j<nums.length;j++){
                sum+=nums[j];
                if(sum==k-nums[i]){
                    count++;
                }
            }
            sum=0;
        }
        return count;
    }
 /*
 输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7
示例 2：
输入：nums = [1], k = 1
输出：[1]
  */
    public int[] maxSlidingWindow(int[] nums, int k) {
        List<Integer> list = new ArrayList<>();
        int l =0;
        int r = k-1;
        int j=l;
        int max =nums[l];
        while(r<nums.length){
            if(j<=r){
                max = max>nums[j]?max:nums[j];
                j++;
            }
            if(j>r){
                list.add(max);
                l++;
                r++;
                j=l;
                if(l<nums.length)
                    max=nums[l];
            }
        }
        int []arr = new int[list.size()];
        for(int i =0;i<arr.length;i++)
            arr[i]=list.get(i);
        return arr;
    }
    public static int[] maxSlidingWindow1(int[] nums, int k){
        int n = nums.length;
        PriorityQueue<int[]> pq = new PriorityQueue<int[]>(new Comparator<int[]>() {
            public int compare(int[] pair1, int[] pair2) {
                return pair1[0] != pair2[0] ? pair2[0] - pair1[0] : pair2[1] - pair1[1];
            }
        });
        for (int i = 0; i < k; ++i) {
            pq.offer(new int[]{nums[i], i});
        }
        int[] ans = new int[n - k + 1];
        ans[0] = pq.peek()[0];
        for (int i = k; i < n; ++i) {
            pq.offer(new int[]{nums[i], i});
            while (pq.peek()[1] <= i - k) {
                pq.poll();
            }
            ans[i - k + 1] = pq.peek()[0];
        }
        return ans;
    }
    /*
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
注意：
对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串，我们保证它是唯一的答案。
示例 1：
输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。
示例 2：
输入：s = "a", t = "a"
输出："a"
解释：整个字符串 s 是最小覆盖子串。
示例 3:
输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。
     */
    Map<Character,Integer> sm = new HashMap<>();
    Map<Character,Integer> tm = new HashMap<>();
    public String minWindow(String s, String t) {
        if (s.length() < t.length())
            return "";
        int l = 0;
        int r = 0;
        int len = Integer.MAX_VALUE, ansL = -1, ansR = -1;
        for(int i=0;i<t.length();i++){
            char c =t.charAt(i);
            tm.put(c,tm.getOrDefault(c,0)+1);
        }
        while(r<s.length()){
            if(tm.containsKey(s.charAt(r)))
                sm.put(s.charAt(r),sm.getOrDefault(s.charAt(r),0)+1);
            while(check()&&l<=r){
                if(r-l+1<len){
                    len=r-l+1;
                    ansL=l;
                    ansR=l+len;
                }
                if(tm.containsKey(s.charAt(l))){
                    sm.put(s.charAt(l),sm.getOrDefault(s.charAt(l),0)-1);
                }
                l++;
            }
            r++;
        }
        return ansL == -1?"":s.substring(ansL,ansR);
    }
    public static String minWindow1(String s, String t) {
        if (s.length() < t.length()||s==null||t==null||s==""||t=="")
            return "";
        int left=0;
        int right=0;
        int needs[] = new int [128];
        int have[] = new int [128];
        int min = s.length()+1;
        int start = 0;
        int count = 0;
        for(int i = 0;i<t.length();i++){
            char c = t.charAt(i);
            needs[c]++;
        }
        while(right<s.length()){
            int r = s.charAt(right);
            if(needs[r]==0){
                right++;
                continue;
            }
            if(have[r]<needs[r]){
                count++;
            }
            have[r]++;
            right++;
            while(count==t.length()){
                if(right-left<min){
                    min = right-left;
                    start = left;
                }
                int l =s.charAt(left);
                if(needs[l]==0){
                    left++;
                    continue;
                }
                if(have[l]==needs[l])
                    count--;
                have[l]--;
                left++;
            }
        }
        if(min==s.length()+1)
            return "";
        return s.substring(start,start+min);
    }
    public boolean check() {
        Iterator iter = tm.entrySet().iterator();
        while (iter.hasNext()) {
            Map.Entry entry = (Map.Entry) iter.next();
            Character key = (Character) entry.getKey();
            Integer val = (Integer) entry.getValue();
            if (sm.getOrDefault(key, 0) < val) {
                return false;
            }
        }
        return true;
    }
}
